package work;

/**
 * 题目：加一。给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一
 */
public class PlusOne {

    public static int[] plusOne(int[] digits) {
        //时间复杂度：O(n)
        //思路：1）进位的条件：digits[i]=9&&+1
        //注意：9 --> 10
        int[] result = new int[digits.length + 1];

        boolean isPlusOne = true;
        for(int i = digits.length - 1; i >= 0; i--){
            if(!isPlusOne){
                break;
            }else{
                if(digits[i] == 9){
                    result[i + 1] = 0;
                    digits[i] = 0;
                    if(i == 0) result[0] = 1;
                }else{
                    digits[i] += 1;
                    result[i + 1] = digits[i];
                    isPlusOne = false;
                }
            }
        }
        return result[0] == 1 ? result : digits;
    }

    public static void main(String[] args) {
        int[] digits = {9};
        int[] result = plusOne(digits);
        for(int d : result){
            System.out.print(d);
        }
    }
}
